import java.util.HashMap;
import java.util.*;

/**
 * 两种水果数的最大数
 * https://leetcode.cn/problems/fruit-into-baskets/
 * 时间复杂度：O(N)
 * 空间复杂度：O（n） 开辟了hash表
 */
class Solution1 {
    public int totalFruit1(int[] fruits) {

        HashMap<Integer,Integer> hashMap = new HashMap<>();

        //1.定义双指针
        int ret = 0;
        for(int left = 0,right = 0;right < fruits.length;right++){

            //2.进窗口
            hashMap.put(fruits[right],hashMap.getOrDefault(fruits[right],0) + 1);

            //判断
            while(hashMap.size() > 2){
                //3.出窗口
                int out = fruits[left];
                hashMap.put(out,hashMap.get(out) - 1);

                if(hashMap.get(fruits[left]) == 0)
                    hashMap.remove(out);
                left++;
            }

            //更新结果
            ret = Math.max(ret, right - left + 1);
        }
        return ret;
    }

    //模拟实现的hash表
    public int totalFruit2(int[] fruits) {

        // HashMap<Integer,Integer> hashMap = new HashMap<>();

        //模拟哈希表
        int[] hash = new int[fruits.length + 1];//存放val值

        //1.定义双指针
        int ret = 0;
        //kinds表示哈希表中的键值《k,v》
        for(int left = 0,right = 0,kinds = 0;right < fruits.length;right++){

            //2.进窗口
            if(hash[fruits[right]] == 0) kinds++;
            hash[fruits[right]]++;

            //判断
            while(kinds > 2){
                //3.出窗口
                int out = fruits[left];
                hash[out]--;//改水果数量减一

                if(hash[out] == 0) kinds--;//该类型的水果数量减完，种类减一
                left++;
            }

            //更新结果
            ret = Math.max(ret, right - left + 1);
        }
        return ret;
    }
}

/**
 *找到字符串中所有字母异位词
 * https://leetcode.cn/problems/find-all-anagrams-in-a-string/
 * 时间复杂度：O（N）
 * 空间复杂度：O（m + n);
 */
class Solution2 {
    public List<Integer> findAnagrams(String s, String p) {
        //准备工作
        char[] s1 = s.toCharArray();
        char[] p1 = p.toCharArray();

        int[] hash1 = new int[26];
        int[] hash2 = new int[26];

        List<Integer> ret = new ArrayList<>();

        for(char ch : p1) hash1[ch - 'a']++;

        //循环遍历
        for(int left = 0,right = 0 ,count = 0;right < s1.length;right++){
            //1.进入窗口
            int in = s1[right] - 'a';
            if(++hash2[in] <= hash1[in]) count++;

            //判断
            if(right - left + 1 > p1.length){
                //2.出窗口
                int out = s1[left++] - 'a';
                if(hash2[out]-- <= hash1[out]) count--;

            }

            //3.更新
            if(count == p1.length) ret.add(left);

        }
        return ret;
    }
}